package com.lzy.arithmetic;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private Node head;
    private Node end;
    private int limit;
    private Map<String, Node> hashMap;

    public LRUCache(int limit) {
        this.limit = limit;
        hashMap = new HashMap<>();
    }

    public String get(String key) {
        Node node = hashMap.get(key);
        if (node == null) {
            return null;
        }
        refreshNode(node);
        return node.value;
    }

    public void remove(String key) {
        Node node = hashMap.get(key);
        removeNode(node);
        hashMap.remove(key);
    }

    public void put(String key, String value) {
        Node node = hashMap.get(key);
        if (node == null) {
            if (hashMap.size() >= limit) {
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }
            Node newNode = new Node(key, value);
            addNode(newNode);
            hashMap.put(key, newNode);
        } else {
            node.value = value;
            refreshNode(node);
        }
    }


    /**
     * 刷新被访问结点位置
     *
     * @param node
     * @return
     */
    private void refreshNode(Node node) {
        if (node == end) {
            return;
        }
        //移除结点
        removeNode(node);
        //重新插入结点
        addNode(node);
    }

    /**
     * 移除链表结点
     *
     * @param node
     * @return
     */
    private String removeNode(Node node) {
        if (node == end) {
            end = end.pre;
        } else if (node == head) {
            head = head.next;
        } else {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }

    /**
     * 尾部链表插入结点
     *
     * @param node
     */
    private void addNode(Node node) {
        if (end != null) {
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        end = node;
        if (head == null) {
            head = node;
        }
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        lruCache.put("001", "用户1信息");
        lruCache.put("002", "用户1信息");
        lruCache.put("003", "用户1信息");
        lruCache.put("004", "用户1信息");
        lruCache.put("005", "用户1信息");

        lruCache.get("002");

        lruCache.put("004", "用户2更新");
        lruCache.put("006", "用户6信息");

        System.out.println(lruCache.get("001"));
        System.out.println(lruCache.get("006"));
    }

}

class Node {
    public Node pre;
    public Node next;
    public String key;
    public String value;

    Node(String key, String value) {
        this.key = key;
        this.value = value;
    }
}
